原始题目:剑指 Offer 32 - I. 从上到下打印二叉树 (opens new window)
从上至下按层打印,明显是二叉树的层序遍历,可以借助队列来实现。
代码:
public int[] levelOrder(TreeNode root) {
List<Integer> ans = new ArrayList<>();
Deque<TreeNode> queue = new LinkedList<>();
if (root != null) {
queue.offer(root);
}
while (!queue.isEmpty()) {
int levelSize = queue.size();
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.poll();
ans.add(node.val);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
int[] arr = new int[ans.size()];
for (int i = 0; i < ans.size(); i++) {
arr[i] = ans.get(i);
}
return arr;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
复杂度分析
- 时间复杂度: 为二叉树的节点总数。
- 空间复杂度:最差情况下,即当树为平衡二叉树时,最多有 个树节点同时在
queue
中,使用 大小的额外空间。